/*--- lquick2.c --------------------------- Listing 5-18 --------
 * Quicksort for linked lists. Uses an insertion
 * sort on small subfiles, eliminates tail
 * recursion to minimize stack usage, and uses
 * a randomly selected pivot to avoid problems
 * with ordered input files.
 *
 * Uses InsertionSortLink() from linsert.c (Listing 5-16)
 *
 * Adapted from an article by Jeff Taylor in
 * C Gazette, Vol 5, No. 6, 1991.
 *
 * #define DRIVER to compile a test driver
 * Driver must be linked to lsortsub.c (Listing 5-13)
 *-------------------------------------------------------------*/

#include <stdlib.h>
#include "lsorthdr.h"

#define DRIVER 1

static CompFunc StoredCompare;
void InsertionSortLink(Node **, Node *, CompFunc);

static void xQuickSortL2(Node **Head, Node *End, int N)
{
    int left_count, right_count, npivot;
    Node **left_walk, *pivot, *old;
    Node **right_walk, *right;

    while (N > 1) {
        if (N <= 9) { /* Insertion sort small lists */
            InsertionSortLink(Head, End, StoredCompare);
            break;
        }

        /* Select a pivot, but not at either end! */
        npivot = abs(rand()) % N;
        if (npivot < 2 || npivot > N - 2)
            npivot = 2;

        /* Run thru the list to the randomly selected point */
        old = *Head;
        while (npivot--)
            old = old->next;
        pivot = old->next;       /* Take as pivot */
        old->next = pivot->next; /* Cut from chain */

        /* Logic is now basically the same as lquick1.c */
        left_walk = Head;    /* Set up left & right halves */
        right_walk = &right;
        left_count = right_count = 0;

        /* Now walk the list */
        for (old = *Head; old != End; old = old->next) {
            if (StoredCompare(old, pivot) < 0) {
                /* Less than pivot, so goes on left */
                left_count += 1;
                *left_walk = old;
                left_walk = &(old->next);
            } else {
                /* Greater than or equal to, so goes on right */
                right_count += 1;
                *right_walk = old;
                right_walk = &(old->next);
            }
        }

        /* Now glue the halves together... */
        *right_walk = End;   /* Terminate right list */
        *left_walk = pivot;  /* Put pivot after things on left */
        pivot->next = right; /* And right list after that */

        /* Now sort the halves in more detail */
        if (left_count > right_count) {
            /*
             * Recursively sort (smaller) right half and then
             * reset local pointers so that when we loop, we
             * will see the left half as the entire list,
             */
            xQuickSortL2(&(pivot->next), End, right_count);
            End = pivot;
            N = left_count;
        } else {
            /* Converse case */
            xQuickSortL2(Head, pivot, left_count);
            Head = &(pivot->next);
            N = right_count;
        }
    }
}

void QuickSortLink(Node **Head, Node *End, CompFunc Compare)
{
    Node *walk;
    int count = 0;
    /* Save address of comparison function */
    StoredCompare = Compare;

    /* Count the list */
    for (walk = *Head; walk != End; walk = walk->next)
        count += 1;

    /* Quicksort the list */
    xQuickSortL2(Head, End, count);
}

#ifdef DRIVER
#include <stdio.h>
#include <string.h>
#include "lsortsub.h"

/*
 * A comparison function
 */
int Cfunc(Node *L, Node *R)
{
    return (strncmp(L->text, R->text, 5));
}

void main(int argc, char *argv[])
{
    Node *ListHead;

    if (argc != 2) {
        fprintf(stderr, "Usage: lquick2 infile\n");
        return;
    }

    if (LoadList(argv[1], &ListHead) == -1)
        return; /* Couldn't load file */

    QuickSortLink(&ListHead, NULL, (CompFunc)Cfunc);
    ShowArray(ListHead, (CompFunc)Cfunc);
}
#endif
